class Solution
{
public:
    long long minimumFuelCost(vector<vector<int>> &roads, int seats)
    {
        int n = roads.size() + 1;
        double seatsD = seats;
        vector<long long> cityPeopleCount(n, 1);
        unordered_map<int, unordered_set<int>> adjTable;
        for (auto &road : roads)
        {
            adjTable[road[0]].insert(road[1]);
            adjTable[road[1]].insert(road[0]);
        }
        unordered_set<int> leafCities;
        for (auto &[city, nearCity] : adjTable)
        {
            if (nearCity.size() == 1)
            {
                leafCities.insert(city);
            }
        }
        leafCities.erase(0);
        long long fuelCost = 0;
        while (!leafCities.empty())
        {
            int leafCity = *leafCities.begin();
            leafCities.erase(leafCity);
            int nearCity = *adjTable[leafCity].begin();
            fuelCost += ceil(cityPeopleCount[leafCity] / seatsD);
            if (nearCity != 0)
            {
                cityPeopleCount[nearCity] += cityPeopleCount[leafCity];
                adjTable[nearCity].erase(leafCity);
                if (adjTable[nearCity].size() == 1)
                {
                    leafCities.insert(nearCity);
                }
            }
        }
        return fuelCost;
    }
};